1. Field of the Invention
The present invention relates to a channel encoder of digital communication system, and more particularly to a convolutional interleaver and method for generating a memory address for reducing the effect of burst errors during data transmission by randomizing an input data stream.
2. Description of the Prior Art
Generally, in a digital communication system, an error correcting technology has been commonly used for detecting and correcting the errors generated during data transmission. The error correcting technology is mainly composed of an error correcting coding (ECC) process in which parity data is added to the transmitted information data at the transmitting end and an interleaving process for rearranging the ordering of coded data to spread apart consecutive errors. When a block code such as Reed-Solomon code out of error correcting codes is employed, information data is divided into a plurality of blocks and redundancy bits are added thereto for detecting and correcting errors in units of block. When a non-block code such as convolutional code is employed, coding is performed according to input sequence and the coded current data is affected by the previous data, which results in better error correcting capabilities than the block code. In the interleaving process, the ordering of data stream coded with either convolutional code or Reed-solomon code is rearranged in a deterministic manner so that the effect of burst errors can be efficiently reduced.
In general, in the digital communication system, the error generated during data transmission is classifed into two types: random errors which are spread apart, and burst errors which comprise a large number of consecutive errors. The error correcting coding (ECC) has an excellent correcting capability for the random errors, however, it is ineffective in presence of burst errors. Accordingly, in most of digital communication systems, an interleaver is equipped for rearranging the original data stream to spread apart the burst errors at the transmitting end, and at least one deinterleaver for recovering the rearranged data stream into the original data stream is provided at the receiving end.
There are two kinds of interleavers a block interleaver and a convolutional interleaver. The block interleaver interleaves the data stream in block units (K.times.L), consisting of K rows and L columns and randomizes the data stream by varying the input/output sequence. That is, the input data stream is horizontally scanned to be stored in a memory and the data stored in the memory is vertically scanned to be outputted. As a result, a bit stream with interleaving level L is inserted between two adjacent data. That is, in the block unit (K.times.L), K is codeword length and L is interleaving level.
In the convolutional interleaver, the input data is temporarily in the memory for a predetermined delay, and the delayed data are inserted between two adjacent data.
FIG. 1 is a diagram illustrating a concept of convolutional interleaver and deinterleaver. The convolutional interleaver 10 is composed of an input switch 11, a plurality of shift registers (I-0) through I-(B-1), and an output switch 12. The convolutional deinterleaver 15 is composed of an input switch 16, a plurality of shift registers D-(B-1) through (D-0), and an output switch 17. Here, data is inputted/outputted to and from the convolutional interleaver 10 and the convolutional deinterleaver 15 in byte units.
The convolutional interleaver has the structure that in the first shift register (I-0), the input and the output are directly connected, such that the length of the shift register is 0, and from the next shift register I-1 to the last shift register I-(B-1) the length of the shift register is M, 2M, 3M, . . . , (B-1)M, such that the length difference between adjacent shift registers is M byte. The convolutional deinterleaver has the inverse structure of the convolutional interleaver.
In (B, M) convolutional interleaver, B indicates the number of the vertical ends of the shift registers, which is called the interleaving level, and M indicates the length difference between the adjacent shift registers.
In the convolutional interleaver 10, the input switch 11 operates in synchronization with the output switch 12, and sequentially switches from the shift register I-0 to the shift register I-(B-1) with B period. According to the switching operation, the first data of B period inputted to the shift register I-0 is outputted without delay, and the second to the last data of B period inputted to the shift registers I-1 to I-(B-1) is outputted after BM, 2BM, . . . , (B-1)BM delay, respectively. Consequently, at the transmitting end, BM number of arbitrary data are inserted between two adjacent data of the input data stream to be transmitted via the channel 13.
In the convolutional deinterleaver 15, the input switch 16 operates in synchronization with the output switch 17 in the same manner as the convolutional interleaver 10. That is, according to the switching operation, the first to the last data of B period inputted to the shift registers D-(B-1) to D-1 is outputted after (B-1)BM, (B-2)BM, . . . , BM delay, and the last data of B period inputted to the shift register D-0 is outputted without delay. Consequently, at the receiving end, after (B-1)BM clock delay, the original data stream is obtained.
The minimal amount of memory (Smin) required for the convolutional interleaver is given by the following mathematical expression 1.